package com.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BST<E extends Comparable<E>>{

    private class Node{
        E e;
        Node left;
        Node right;

        public Node(E e){
            this.e = e;
            left = null;
            right = null;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "e=" + e +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

    private Node root;
    private int size;

    public int getSize(){
        return size;
    }

    public void add(E e){
        root = add(root,e);
    }

    /**
     * 在以root为根的树中，插入e
     * @param root
     * @param e
     * @return 返回插入结点（新的子树的根节点）
     */
    private Node add(Node root, E e) {
        if (root == null){
            size++;
            return new Node(e);
        }

        if (e.compareTo(root.e)<0){
            root.left = add(root.left,e);
        } else if (e.compareTo(root.e)>0){
            root.right = add(root.right, e);
        }
        return root;
    }


    public Node search(E e){
        return search(root,e);
    }
    private Node search(Node node,E e){
        if (node == null||node.e.compareTo(e)==0){
            return node;
        }
        if (e.compareTo(node.e)<0){
            return search(node.left,e);
        }else {
            return search(node.right,e);
        }
    }

    public Node searchParent(E e){
        return searchParent(root,e);
    }

    private Node searchParent(Node node,E e){
        if (node == null||node.e.compareTo(e)==0)
            return null;
        if (e.compareTo(node.e)<0){
            if (node.left!=null&&node.left.e.compareTo(e)==0){
                return node;
            }
            return searchParent(node.left,e);
        }else {
            if (node.right!=null&&node.right.e.compareTo(e)==0){
                return node;
            }
            return searchParent(node.right,e);
        }

    }

    public void preOrder(){
        preOrder(root);
    }
    private void preOrder(Node root){
        if (root == null)
            return;
        else {
            System.out.println(root.e);
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    public void preOrderWhile(){
        preOrderWhile(root);
    }

    private void preOrderWhile(Node root){
        if (root == null)
            return;
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            Node node = stack.pop();
            System.out.println(node.e);
            if (node.right!=null)
                stack.push(node.right);
            if (node.left!=null)
                stack.push(node.left);
        }
    }
    public void levelOrder(){
        levelOrder(root);
    }
    private void levelOrder(Node root){
        if (root == null)
            return;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            Node node = queue.poll();
            System.out.println(node.e);
            if (node.left!=null)
                queue.add(node.left);
            if (node.right!=null)
                queue.add(node.right);
        }
    }

    public void delete(E e){
        delete(root,e);
    }

    private void delete(Node root,E e){
        if (root == null)
            return;
        Node node = search(root,e);
        if (node == null)
            return;
        Node parent = searchParent(root, e);
        if (node.left==null&&node.right==null){
            if (parent!=null&&e.compareTo(parent.e)<0){
                parent.left = null;
            }else if (parent!=null&&e.compareTo(parent.e)>0){
                parent.right = null;
            }else {
                node.e = null;
            }
        }else if(node.left!=null&&node.right!=null){
            Node minNode = searchRightMin(node.right);
            node.e = minNode.e;
            delete(node.right,minNode.e);
        }else {
            if (node.left!=null){
                if (e.compareTo(parent.left.e)==0){
                    parent.left = node.left;
                }else {
                    parent.right = node.left;
                }
            }else {
                if (e.compareTo(parent.right.e)==0){
                    parent.right = node.right;
                }else {
                    parent.left = node.right;
                }
            }
        }
    }

    private Node searchRightMin(Node right) {
        if (right == null||right.left==null)
            return right;
        return searchRightMin(right.left);
    }

    private Node searchLeftMax(Node left){
        if (left == null||left.right == null)
            return left;
        return searchLeftMax(left.right);
    }

    public void deletePlus(E e){
        deletePlus(root,e);
    }

    private Node deletePlus(Node root,E e){
        if (root == null)
            return null;
        if (e.compareTo(root.e)<0){
           root.left = deletePlus(root.left, e);
           return root;
        }else if (e.compareTo(root.e)>0){
           root.right = deletePlus(root.right, e);
           return root;
        }else {
           if (root.left == null){
               Node right = root.right;
               root.right = null;
               return right;
           }
           if (root.right == null){
               Node left = root.left;
               root.left = null;
               return left;
           }
           Node rightMin = searchRightMin(root.right);
           root.e = rightMin.e;
           root.right = deletePlus(root.right,rightMin.e);
           return root;
        }
    }

    @Override
    public String toString() {
        return "BST{" +
                "root=" + root +
                ", size=" + size +
                '}';
    }
}
